package 线;

import com.cc.User;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author DeepSeek
 * @date 2025/6/28
 * 用户关系树遍历工具类(防循环引用)
 */
public class TreeTraversal {

    /**
     * 构建用户关系的子节点映射表
     * @param userList 用户列表
     * @return Map<父ID, List<子用户>>
     * putIfAbsent方法 这是Map的一个方法，意思是"如果不存在则放入"
     */
    private static Map<Integer, List<User>> buildChildMap(List<User> userList) {
        Map<Integer, List<User>> childMap = new HashMap<>();
        for (User user : userList) {
            childMap.putIfAbsent(user.getPid(), new ArrayList<>());
            childMap.get(user.getPid()).add(user);
            // childMap.computeIfAbsent(user.getPid(), k -> new ArrayList<>()).add(user);
        }
        return childMap;
    }

    /**
     * 获取所有下级推广用户ID(广度优先遍历)
     * @param userList 用户列表
     * @param rootId 起始用户ID
     * @return 所有下级用户ID列表
     */
    public static List<Integer> bfsTeam(List<User> userList, Integer rootId) {
        Map<Integer, List<User>> childMap = buildChildMap(userList);
        List<Integer> result = new ArrayList<>();
        Set<Integer> visited = new HashSet<>(); // 记录已访问节点
        Queue<Integer> queue = new LinkedList<>();

        if (rootId != null) {
            queue.offer(rootId);
            visited.add(rootId);
        }

        while (!queue.isEmpty()) {
            Integer currentId = queue.poll();
            List<User> children = childMap.get(currentId);
            if (children != null) {
                for (User child : children) {
                    if (!visited.contains(child.getId())) {
                        result.add(child.getId());
                        queue.offer(child.getId());
                        visited.add(child.getId());
                    }
                }
            }
        }
        return result;
    }

    /**
     * 获取所有下级推广用户ID(深度优先遍历)
     * @param userList 用户列表
     * @param rootId 起始用户ID
     * @return 所有下级用户ID列表
     */
    public static List<Integer> dfsTeam(List<User> userList, Integer rootId) {
        Map<Integer, List<User>> childMap = buildChildMap(userList);
        List<Integer> result = new ArrayList<>();
        Set<Integer> visited = new HashSet<>(); // 记录已访问节点 解决循环引用问题
        Deque<Integer> stack = new ArrayDeque<>();

        if (rootId != null) {
            stack.push(rootId);
            visited.add(rootId);
        }

        while (!stack.isEmpty()) {
            Integer currentId = stack.pop();
            List<User> children = childMap.get(currentId);
            if (children != null) {
                // 反向遍历以保证顺序与递归DFS一致
                for (int i = children.size() - 1; i >= 0; i--) {
                    User child = children.get(i);
                    if (!visited.contains(child.getId())) {
                        result.add(child.getId());
                        stack.push(child.getId());
                        visited.add(child.getId());
                    }
                }
            }
        }
        return result;
    }

    /**
     * 优化后的DFS实现，使用Map预先构建父子关系映射，避免多次遍历列表
     * @param list
     * @param id
     * @return
     * 预构建 Map，避免重复遍历, 最高效的写法（推荐生产环境使用）
     */
    public static List<Integer> myTeamOptimized(List<User> list, Integer id) {
        List<Integer> result = new ArrayList<>();
        if (list == null || id == null) return result;

        // 预构建 pid → List<childIds> 的映射，避免递归时反复遍历 list
        Map<Integer, List<Integer>> pidToChildren = list.stream()
                .collect(Collectors.groupingBy(
                        User::getPid,
                        Collectors.mapping(User::getId, Collectors.toList())
                ));

        // 递归查找所有子节点
        myTeamHelper(pidToChildren, id, result);
        return result;
    }

    private static void myTeamHelper(Map<Integer, List<Integer>> pidToChildren, Integer id, List<Integer> result) {
        List<Integer> children = pidToChildren.get(id);
        if (children != null) {
            result.addAll(children);
            children.forEach(childId -> myTeamHelper(pidToChildren, childId, result));
        }
    }

    public static void main(String[] args) {
        // 测试数据(包含循环引用: 1→2→3→1)
        List<User> userList = Arrays.asList(
                new User(1, 0),
                new User(2, 1),
                new User(3, 2),
                new User(4, 2),
                new User(5, 3),
                new User(6, 3),
                new User(7, 0),
                new User(8, 7),
                new User(1, 3) // 循环引用: 1的父节点是3
        );

        System.out.println("BFS结果(从1开始): " + bfsTeam(userList, 1));
        System.out.println("DFS结果(从3开始): " + dfsTeam(userList, 3));
        System.out.println("BFS结果(从不存在节点开始): " + bfsTeam(userList, 999));

        List<Integer> teamMembers = myTeamOptimized(userList, 3);
        System.out.println("优化后DFS结果(从3开始): " + teamMembers);
    }
}